class Solution:
    def maximumScore(self, cards, cnt):
        # 单次遍历分离奇数和偶数
        odds = []
        evens = []
        for num in cards:
            if num % 2 == 1:
                odds.append(num)
            else:
                evens.append(num)

        # 部分排序：只取最大的min(cnt, len)个元素
        odds.sort(reverse=True)
        evens.sort(reverse=True)
        odds = odds[:cnt]
        evens = evens[:cnt]

        # 预计算前缀和
        prefix_odds = [0] * (len(odds) + 1)
        for i in range(len(odds)):
            prefix_odds[i + 1] = prefix_odds[i] + odds[i]

        prefix_evens = [0] * (len(evens) + 1)
        for i in range(len(evens)):
            prefix_evens[i + 1] = prefix_evens[i] + evens[i]

        max_sum = 0
        # 遍历可能的奇数个数k（0,2,...,min(cnt, len(odds))）
        max_k = min(cnt, len(odds))
        for k in range(0, max_k + 1, 2):
            if cnt - k <= len(evens):
                current_sum = prefix_odds[k] + prefix_evens[cnt - k]
                if current_sum > max_sum:
                    max_sum = current_sum
        return max_sum
